package com.yulongtian.algorithms.data_structure.level1;

import java.util.Arrays;
import java.util.Comparator;

/**
 * https://leetcode.cn/problems/two-sum?envType=study-plan&id=shu-ju-jie-gou-ru-men&plan=data-structures&plan_progress=fuuvsvi
 * 可
 *
 * @author yulongTian
 * @create 2023-03-02 9:43
 */
public class Test02 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSum(new int[]{3, 3}, 6)));
    }

    public static int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        int[][] num_index = new int[len][2];
        for (int i = 0; i < nums.length; i++) {
            num_index[i][0] = nums[i];
            num_index[i][1] = i;
        }

        int[] ans = new int[2];
        Arrays.sort(num_index, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            if (num_index[left][0] + num_index[right][0] == target) {
                ans[0] = num_index[left][1];
                ans[1] = num_index[right][1];
                break;
            } else if (num_index[left][0] + num_index[right][0] > target) {
                right--;
            } else {
                left++;
            }
        }
        return ans;
    }

}
